package DoExercise.HSP_ZCY.A008_树.A001_普通二叉树;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: Du
 * @Date: 2021/7/13 12:21
 * <p>
 * <p>
 * 求树的最大宽度
 * <p>
 * 建立一种发现每个层共有多个节点的机制
 */
public class C10_二叉树的最大宽度
{
    public static void main(String[] args)
    {
        int maxLevel = 10;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++)
        {
            Node head = generateRandomBST(maxLevel, maxValue);
            if (maxWidthUseMap(head) != maxWidthNoMap(head))
            {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }
    
    public static class Node
    {
        public int value;
        public Node left;
        public Node right;
        
        public Node(int data)
        {
            this.value = data;
        }
    }
    
    
    /**
     * 求树的最大宽度
     * <p>
     * 用map将同一层的节点的层数记录，层数相同的节点一起统计，否则建立新的统计信息，最后统计最大层的信息
     * <p>
     * 用Map实现
     *
     * @param head
     * @return
     */
    public static int maxWidthUseMap(Node head)
    {
        if (head == null) return 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        HashMap<Node, Integer> levelMap = new HashMap<>();
        levelMap.put(head, 1);
        int curLevel = 1;//当前层数
        int curLevelNodes = 0;//curLevel当前层的宽度
        int max = 0;
        while (!queue.isEmpty())
        {
            Node cur = queue.poll();
            int curNodeLevel = levelMap.get(cur);
            if (cur.left != null)
            {
                levelMap.put(cur.left, curNodeLevel + 1);
                queue.add(cur.left);
            }
            if (cur.right != null)
            {
                levelMap.put(cur.right, curNodeLevel + 1);
                queue.add(cur.right);
            }
            
            if (curNodeLevel == curLevel)
            {
                curLevelNodes++;
            } else
            {
                max = Math.max(max, curLevelNodes);
                curLevel++;
                curLevelNodes = 1;
            }
        }
        max = Math.max(max, curLevelNodes);
        return max;
    }
    
    
    public static int maxWidthNoMap(Node head)
    {
        if (head == null) return 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        Node curEnd = head;//当前层最右节点
        Node nextEnd = null;//下一层的最右节点
        int max = 0;
        int curLevelNodes = 0;
        while (!queue.isEmpty())
        {
            Node cur = queue.poll();
            if (cur.left != null)
            {
                queue.add(cur.left);
                nextEnd = cur.left;//标记当前曾的最后一个节点
            }
            if (cur.right != null)
            {
                queue.add(cur.right);
                nextEnd = cur.right;//标记当前曾的最后一个节点
            }
            curLevelNodes++;//每次出队时就统计个数
            if (cur == curEnd)//统计到最后一个节点，就重新统计下一层
            {
                max = Math.max(max, curLevelNodes);
                curLevelNodes = 0;
                curEnd = nextEnd;
            }
        }
        return max;
    }
    
    public static Node generateRandomBST(int maxLevel, int maxValue)
    {
        return generate(1, maxLevel, maxValue);
    }
    
    public static Node generate(int level, int maxLevel, int maxValue)
    {
        if (level > maxLevel || Math.random() < 0.5) return null;
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }
    
    
}
